約 4,976,322 件
https://w.atwiki.jp/cwc_dat2/pages/76.html
アサシンクリードブラッドライン アサシンクリードブラッドラインID+ゲーム名所持金最大 ナイフ投げ放題 ID+ゲーム名 _S ULJM-05571 _G Assassins_Creed_Blood_Lines 所持金最大 _C0 MONEY MAX _L 0x112DC028 0x0000270F ナイフ投げ放題 _C0 knife inf _L 0x012DC021 0x00000005
https://w.atwiki.jp/cwcwiki/pages/473.html
アサシンクリードブラッドライン アサシンクリードブラッドラインID+ゲーム名所持金最大 ナイフ投げ放題 ID+ゲーム名 _S ULJM-05571 _G Assassins_Creed_Blood_Lines 所持金最大 _C0 MONEY MAX _L 0x112DC028 0x0000270F ナイフ投げ放題 _C0 knife inf _L 0x012DC021 0x00000005
https://w.atwiki.jp/gamekoryaku/pages/360.html
Assassin s Creed Bloodlines (アサシン クリード ブラッドライン)の攻略 Assassin's Creed Bloodlines (アサシン クリード ブラッドライン)の攻略ゲーム 攻略本・サウンドトラックなど 攻略サイト その他 ゲーム パッケージ メーカー公式HP 価格 発売日 備考 ユービーアイ ソフト 公式HP Sony PSP ￥ 5,229 2009/12/23 攻略本・サウンドトラックなど 表紙 タイトル 出版 価格 発売日 備考 攻略サイト サイト名をクリックで攻略サイトへ移動します。 サイト名 感想 アサシン クリード ブラッドライン攻略WIKI その他 戻る
https://w.atwiki.jp/assassins_creed/pages/13.html
アサシンクリードは、アサシン教団とテンプル騎士団がその思想の違いから、古くから現在に至るまで続けてきた争いを描く物語であり、ゲーム本編は常に現代の人物がアニムスないしヘリックスを用い、過去の人物の記憶を追体験する、という構造になっている（スピンオフ作品を除く）。 しかし、ゲーム内のボリュームとしては過去編が圧倒的な量を占めており、現代編はあまり描かれていない。 現在、現代編はタイタンコミックスから出版されるコミック（下記一覧の Assassin s Creed Assassins 以降の作品）を中心に展開されている。 この中でもAssassin s Creed Assassins、Assassin s Creed Templars、Assassin s Creed FCBD 2016 Edition、Assassin s Creed Uprisingの4作品は、近作のゲーム内で描かれる現代編及びその登場人物とも特に関連性の高い作品である。 （なのでこの4作品から優先的に記事を作成します） 作品一覧 Assassin s Creed (comic) Assassin s Creed (web comic) Assassin s Creed (French comics) Assassin s Creed The Fall Assassin s Creed The Chain アサシンクリード4 ブラックフラッグ 覚醒（Assassin s Creed Awakening） Assassin s Creed Brahman]] Assassin s Creed Assassins Assassin s Creed Templars Assassin s Creed FCBD 2016 Edition Assassin s Creed Last Descendants - Locus Assassin s Creed Uprising Assassin s Creed Reflections Assassin s Creed Origins
https://w.atwiki.jp/assassins_creed/pages/2.html
メニュー トップページ アサシンクリード関連作品一覧ゲーム 小説 コミック 映画 短編映画 アニメ 用語集組織 人物 エデンの秘宝 その他 リンク @wiki @wikiご利用ガイド ここを編集
https://w.atwiki.jp/tenkai_cr/pages/602.html
アサシンクリード2 ユービーアイソフト ジャンル アクションアドベンチャー・ステルス 発売日 2009年12月3日 価格 7,329円 （税込） 396：名無しさん必死だな：2009/12/06(日) 01 32 19 ID 4z2LheH5P アサシンクリード２、前作をかなり正統的にボリュームアップさせた感じ。 なので、逆に言うと大作に疲れるって人にはちょっとアレかもだが。 大作に浸りたい人にはおすすめかな。 前作にもあったアイテム収集、あと本拠地のデコレーションとやりこみ要素も充実。 397：名無しさん必死だな：2009/12/06(日) 01 33 31 ID 8t/PIwkG0 アサクリは進化しまくってたなぁ まだ途中だけど、暗殺モーションが増えてていいね。 痒い所に手が届いた感じ。 398：名無しさん必死だな：2009/12/06(日) 01 45 05 ID Gt8crSjj0 前作は惜しい名作って感じだったがそんなに良くなってるのか アイテム収集は前作にもっていうか、1の場合は旗集めだよね・・・ 確か2は武器装備も購入できるんだっけ。これは買わないとダメか メイス縛りとかできるのかな？暗殺はアサシンブレード使わないと無理？ 399：名無しさん必死だな：2009/12/06(日) 01 50 47 ID NMZVxb2A0 398 使わなくても殺人シーン突入できたはず 武器もアイテムも服装も豊富よぉ 個人的に街育成要素が楽しかったりｗ 400：名無しさん必死だな：2009/12/06(日) 01 55 44 ID 8t/PIwkG0 街育成で時折お金が入るのがうれしい。 しかし、このペースだと途中で金余りそうだな……。 前作はなかなか人に薦めるのは難しかったけど、今回は結構いけそうだ＞アサクリ２ 402：名無しさん必死だな：2009/12/06(日) 02 10 29 ID Gt8crSjj0 公式サイトいってきた ttp //www.ubisoft.co.jp/assassinscreed2/index.html なるほど街の育成やら悪名の増減やら色々増えたようね サイトの方も舞台の時代背景の説明やら結構充実してるね アサシン診断で主人公になって少し嬉しかったりｗ 朝になったら買ってくるか リファレンスガイドもう無くなってるかなー 403：名無しさん必死だな：2009/12/06(日) 02 17 40 ID NMZVxb2A0 402 なくても勿論楽しめるけど あれの出来凄まじいよ 攻略本＋資料集＋薀蓄辞典な感じで
https://w.atwiki.jp/revelations/pages/63.html
アサシン勧誘 アサシン勧誘ケンカ屋 弟子 復讐 軽業 物乞い スリ ケンカ屋 腕自慢にケンカをふっかけられた。この男に謙虚さという言葉の意味を教えてやらなければ 弟子 この若者は、自分はアサシンだと言い張っている。競争に勝ち、本物のすごさを教えてやらなければ 復讐 この男はならず者によって重傷を負わされた。そして今、彼の家族にも危険が迫っている。ならず者を見つけ、更なる悲劇を未然に防がなければ 軽業 軽業師の女性が理由もなく番兵たちの嫌がらせを受けている。彼女を守らなければ 物乞い 泥棒を追いかけ、捕らえなければ スリ 荒稼ぎしているスリがいる。見つけ出し、話をしなければ
https://w.atwiki.jp/acbhood/
アサシンクリード ブラザーフッド 攻略ガイドWIKI
https://w.atwiki.jp/cryptospace/pages/19.html
はじめに 準備 一方向関数とランダムオブジェクト 公開鍵暗号 IDベース暗号 属性ベース暗号 検索可能暗号 デジタル署名 認証プロトコル ストレージ証明 鍵共有プロトコル コミットメント 汎用的結合可能性 Obfuscators 暗号的クラウドストレージ 文献 演習問題 by 有田 正剛
https://w.atwiki.jp/cryptospace/pages/20.html
公開鍵暗号とその安全性定義識別不可能性選択平文攻撃に対する識別不可能性 選択暗号文攻撃に対する識別不可能性 頑健性 安全な公開鍵暗号の構成選択平文攻撃に対し識別不可能な公開鍵暗号の構成トラップドア置換にもとづく構成 エルガマル暗号 ランダムオラクルモデルにもとづく構成 適応的選択暗号文攻撃に対し識別不可能な公開鍵暗号の構成ジェネリックな構成 ランダムオラクルモデルにもとづく構成CCAinRO 平文検査攻撃における一方向性 REACT 双子エルガマル暗号 ランダムオラクルモデルを必要としない構成Cramer-Shoup暗号 Camenish-Shoup暗号 タグベース暗号タグ選択暗号文攻撃に対する識別不可能性 タグベース暗号から公開鍵暗号への変換 タグ選択暗号文攻撃に対し識別不可能なタグベース暗号の構成判定線形仮定 判定線形仮定にもとづくタグ選択暗号文攻撃に対し識別不可能なタグベース暗号 公開鍵暗号とその安全性定義 公開鍵暗号とは効率的な確率的アルゴリズムの3つ組(Gen, Enc, Dec)である： (pk, sk) ← Gen(1n) c ← Enc(pk, m) m ← Dec(sk, c). 完全性(completeness)条件として、メッセージ空間Mに含まれる全てのメッセージmについて Pr[ (pk, sk) ← Gen(1n), c ← Enc(pk, m), m ← Dec(sk, c) m = m ] = 1 を要求する。 識別不可能性 選択平文攻撃に対する識別不可能性 暗号文がメッセージのどのような部分情報も漏らさないとき、その暗号は識別不可能であるという。 より正確に定義するために、公開鍵暗号Π=(Gen,Enc,Dec)とそれに対する攻撃者Aについて以下の試行を定義する： 試行 CPAΠ,A(n) (pk, sk) ← Gen(1n) pkを入力として攻撃者Aを起動する。 Aから同じ長さの2つのメッセージからなるチャレンジクエリ(m0,m1)を受け取ったら（チャレンジクエリは一度のみ許される）、 0または1をランダムに選択し、bとする。 mbをpkで暗号化し、c*をえる： c* ← Enc(pk, mb)。 c*をチャレンジクエリに対する応答として返す。 Aが出力b で終了したら、b =? b の１ビットを出力とする。 定義(IND-CPA) 公開鍵暗号Πが選択平文攻撃に対し識別不可能（IND-CPA）であるとは、 任意の効率的な撃者Aについて、その識別利得 ｜ Pr[ CPAΠ,A(n) = 1 ] - 1/2 ｜ がネグリジブルであることをいう。 （確率Pr[ CPAΠ,A(n) = 1 ]をAの成功確率と呼ぶ。） もしも、暗号文c*からもとのメッセージの情報が漏れていれば、それを用いて攻撃者Aはもとのメッセージがm0なのかm1なのか、 推測できるはずである。 選択暗号文攻撃に対する識別不可能性 公開鍵暗号を通信環境におけるアプリケーションで利用するためには、 「復号オラクル」を用いることができる、より強力な攻撃者を想定する必要がある。 公開鍵暗号Π=(Gen,Enc,Dec)とそれに対する攻撃者Aについて以下の試行を定義する。 試行 CCAΠ,A(n) (pk, sk) ← Gen(1n) pkを入力として攻撃者Aを起動する。 Aから同じ長さの2つのメッセージからなるチャレンジクエリ(m0,m1)を受け取ったら（チャレンジクエリは一度のみ許される）、 0または1をランダムに選択し、bとする。 mbをpkで暗号化し、c*をえる： c* ← Enc(pk, mb)。 c*をチャレンジクエリに対する応答として返す。 Aから復号クエリcを受け取ったら（復号クエリは何度でも許される）、 (c*がすでに定義されていて) c = c* なら⊥を応答する。 c = c* でないならば、その復号結果m ← Dec(sk, c)を応答する。 Aが出力b で終了したら、b =? b の１ビットを出力とする。 定義(IND-CCA2) 公開鍵暗号Πが適応的選択暗号文攻撃に対し識別不可能（IND-CCA2）であるとは、 任意のPPT攻撃者Aについて、その識別利得 ｜ Pr[ CCAΠ,A(n) = 1 ] - 1/2 ｜ がネグリジブルであることをいう。 （確率Pr[ CPAΠ,A(n) = 1 ]をAの成功確率と呼ぶ。） 適応的選択暗号文攻撃では、 攻撃者Aは、チャレンジャーから受け取った暗号文c*に関連付けて、別の暗号文c を生成する。 復号オラクルを用いてその復号文m を得る。 m からもとの暗号文c*の復号文mbを推測する といった攻撃が典型的である。 上の定義で、攻撃者Aの復号クエリがチャレンジクエリ以前に限定されるとき、 公開鍵暗号Πは非適応的選択暗号文攻撃に対し識別不可能（IND-CCA1）であるという。 頑健性 定義(BR93) 公開鍵暗号Πが頑健であるとは、任意のPPT関係ρ, PPT攻撃者(F,A)に対し、あるシミュレータA*が存在し、 以下のε(k) - ε*(k)がネグリジブルであることをいう： ε(k) = Pr[ (pk,sk) ← Gen(1n), π← F(pk), x ← π, α ← Enc(pk,x), α ← A(pk,π,α) ρ(x, Dec(sk,α ))=1 ] ε*(k) = Pr[ (pk,sk) ← Gen(1n), π← F(pk), x ← π, α ← A*(pk,π) ρ(x, Dec(sk,α ))=1 ] ただし、関係ρは任意のxについて ρ(x,x) = ρ(x,⊥) = 0 であるものとする。 安全な公開鍵暗号の構成 選択平文攻撃に対し識別不可能な公開鍵暗号の構成 トラップドア置換にもとづく構成 定義 (G, {fi}i)がトラップドア置換であるとは、任意の (i, ti) ← G(1n) について、 fi {0,1}n → {0,1}n は一方向置換である。 tiを知っていたら、fi-1(・) は効率的に計算可能である。 ことをいう。tiを（fiの）トラップドアという。 RSA仮定のもとで、RSA関数 fe,N(x) = xe mod N は（dをトラップドアとする）トラップドア置換である。 構成(CPA暗号) (G, {fi}i) トラップドア置換 hci fiのハードコア述語 Gen(1n) (pk, sk) = (i, ti) ← G(1n). Enc(pk = i, m) // m∈{0,1}l r ← {0,1}n fi(r), fi2(r), ..., fil(r) を計算。 p = ( hci(fil-1(r)), hci(fil-2(r)), ..., hc(r) ) return c = (m + p, fil(r)). Dec(sk = ti, c = (m , w)) tiを用いて w=fil(r) から r を求める。 p = ( hci(fil-1(r)), hci(fil-2(r)), ..., hc(r) ) return m - p. 定理(CPA暗号) {fi}iが、ハードコア述語{hci}iをもつ、トラップドア置換ならば、 構成(CPA暗号)の公開鍵暗号は選択平文攻撃に対し識別不可能（IND-CPA）である。 証明 エルガマル暗号 (ga,gb)が与えられて、gabを求める問題を計算DH問題と呼ぶ。 計算DH問題は困難であるとの仮定を計算DH仮定という。より正確には、 仮定(CDH仮定) 群生成アルゴリズムGenGに対して計算DH仮定が成り立つとは、 任意の効率的なアルゴリズムAについて、その成功確率 Pr[s=(q,g) ← GenG(1n), a,b ← Zq ： A(s, ga,gb) = gab] がネグリジブルであることをいう。 離散対数問題が解ければ計算DH問題も解けるので、 （すなわち、計算DH問題は離散対数問題ほどには難しくないので、） 計算DH仮定は離散対数仮定より強い仮定である。 計算DH問題は、その答えが与えられてもそれとはわからい（ほどに難しい）、という仮定を判定DH仮定という。 より正確には、 仮定(DDH仮定) 群生成アルゴリズムGenGに対して判定DH仮定が成り立つとは、 任意の効率的なアルゴリズムDについて、その識別利得 ｜ Pr[s=(q,g) ← GenG(1n), a,b ← Zq ： D(s, ga,gb,gab)) = 1] - Pr[s=(q,g) ← GenG(1n), a,b,c ← Zq ： D(s, ga,gb,gc)) = 1] ｜ がネグリジブルであることをいう。 (ga,gb,gab)の形の3つ組をDHタプルと呼ぶ。 注意 判定DH仮定のもとで、 Gg,ga(x) =def (gx, gax) は疑似乱数生成器。 構成(エルガマル暗号) GenG(1n) 群生成アルゴリズム Gen(1n) (q, g) ← GenG(1n), x ← Zq, y = gx pk=(q,g,y), sk = (q,g,x). Enc(pk=(q,g,y), m) // m∈ g r ← {0,q-1}, c1 = gr, c2 = m yr return c = (c1, c2). Dec(sk=(q,g,x), c=(c1, c2)) return c2/c1x. 定理(エルガマル暗号) 群生成アルゴリズムGenGが判定DH仮定を満たすならば、エルガマル暗号は選択平文攻撃に対し識別不可能（IND-CPA）である。 証明 ランダムオラクルモデルにもとづく構成 ハッシュ関数G {0,1}* → {0,1}l への呼び出しをランダムオラクルOG(・)への呼び出しに 置き換えてしまう（アルゴリズムの実行）モデルを（Gについての）ランダムオラクルモデルと呼ぶ。 構成(ランダムオラクル) OG 初期化： lビット出力の関数Gをランダムに選択する。 ※ 値xごとに独立なlビット乱数G(x)を選択することと同じ。 問い合わせ x を受け取ったら、 G(x) を返す。 構成(CPAinRO) (Genf, {fi}i) トラップドア置換 Gen(1n) (i,ti) ← Genf(1n) ハッシュ関数 G {0,1}* → {0,1}l を選択 return pk=(i,G), sk = (ti,G). Enc(pk=(i,G), m) // m∈{0,1}l r ← {0,1}n return c = (fi(r), G(r)+m). Dec(sk=(ti,G), c=(y, s)) tiを用いて、r ← fi-1(y) return s - G(r). 定理(CPAinRO) ハッシュ関数Gについてのランダムオラクルモデルにおいて、 {fi}iがトラップドア置換ならば、構成(CPAinRO)は選択平文攻撃に対し識別不可能（IND-CPA）である。 証明 適応的選択暗号文攻撃に対し識別不可能な公開鍵暗号の構成 ジェネリックな構成 構成(DDN) (Gen,Enc,Dec) 選択平文攻撃に対し識別不可能な公開鍵暗号 (P, V) 言語Lに対する非対話零知識証明システム ： L = {(c1,...,cn) | ∃m,(w1,...,wn) s.t. ci = Enc(pki, m; wi)} ※ 簡単のため、pkiはciに含まれているとする。 (SigGen, Sign, Verify) ワンタイム署名 公開鍵暗号(Gen , Enc , Dec ) Gen (1n) r ← {0,1}poly(n) i ∈ [1..n] (pki,0,ski,0) ← Gen(1n), (pki,1,ski,1) ← Gen(1n) pk = (r, (pk1,0,...,pkn,0 | pk1,1,...,pkn,1)), sk = (sk1,0,...,skn,0 | sk1,1,...,skn,1). Enc (pk, m) (vk,sk) ← SigGen(1n), (v1,...,vn) = vk i ∈ [1..n] wi ← {0,1}*, ci = Enc(pki,v_i, m; wi) C = (c1,...,cn) Π ← P(r, C, (m,(w1,...,wn))), σ ← Sign(sk, (C,Π)) return (vk,C,Π,σ). Dec (sk,(vk,C,Π,σ)) Verify(vk,(C,Π),σ) =? 0 return ⊥ else V(r,C,Π) =? 0 return ⊥ else return Dec(sk1,vk_1,c1). 定理(DDN) (Gen,Enc,Dec)が選択平文攻撃に対し識別不可能な公開鍵暗号で、 (P,V)が上記の言語Lに対する適応的安全な非対話零知識証明システムで、 (SigGen, Sign, Verify)がストロングワンタイム署名ならば、 (Gen ,Enc ,Dec )は適応的選択暗号文攻撃に対し識別不可能な公開鍵暗号である。 ランダムオラクルモデルにもとづく構成 CCAinRO 構成(CCAinRO) [BR 93] [部品] トラップドア置換 (Genf, {fi}i) ハッシュ関数 G {0,1}* → {0,1}l ハッシュ関数 H {0,1}* → {0,1}n [スキーム] Gen(1n) (i,ti) ← Genf(1n) return pk=(i,G,H), sk = (ti,G,H) Enc(pk=(i,G,H), m) ※ m∈Bl. r ← {0,1}n return c = (fi(r), G(r)+m, H(r,m)) Dec(sk=(ti,G,H), c=(a,w,b)) tiを用いて、r ← fi-1(a) m = w - G(r) H(r,m) =? b return m else return ⊥ 定理(CCAinRO) [BR 93] ハッシュ関数GおよびHに対するランダムオラクルモデルにおいて、 {fi}iがトラップドア置換ならば、 構成(CCAinRO)は適応的選択暗号文攻撃に対し識別不可能である。 証明 定理(NMinRO) [BR 93] ハッシュ関数GおよびHに対するランダムオラクルモデルにおいて、 {fi}iがトラップドア置換ならば、構成(CCAinRO)は(BR93の意味で)頑健である。 証明 この構成はトラップドア置換を用いているので、たとえばエルガマル暗号には適用できない。 平文検査攻撃における一方向性 平文と暗号文の対(c,m)を受け取ると、暗号文cの復号結果が平文mと一致するか否かの1ビットだけを 教えてくれるオラクルを平文検査オラクル(PCO)と呼ぶ。 平文検査オラクルを用いることができても、一方向性をたもつ公開鍵暗号を平文検査攻撃に対し一方向であるという。 より正確には： 定義(OW-PCA) 公開鍵暗号(Gen,Enc,Dec)が平文検査攻撃に対し一方向（OW-PCA）であるとは、 任意の効率的な撃者Aについて、その成功確率 Pr[ (pk,sk) ← Gen, m ← M, y ← Enc(pk,m), m ← APCO(sk,・)(y) ： m = m ] がネグリジブルであることをいう。 Gap仮定（判定DH問題を解くオラクルが与えられても、計算DH問題は難しい）のもとで、 エルガマル暗号は平文検査攻撃に対し一方向である。 REACT 構成(REACT) [OP01] (Gen,Enc,Dec) 平文検査攻撃に対し一方向である公開鍵暗号 G {0,1}* → {0,1}l ハッシュ関数 H {0,1}* → {0,1}k ハッシュ関数 REACT = (Gen , Enc , Dec ) Gen () (pk, sk) ← Gen(). Enc (pk, m) // m ∈ {0,1}l r ← M, a ← Enc(pk, r) // Mは(Gen,Enc,Dec)のメッセージ空間 b = m + G(r), c = H(r, m, a, b) return C = (a, b, c). Dec (sk, C=(a,b,c)) r ← Dec(sk, a), m = b - G(r) c =? H(r, m, a, b) return m else return ⊥. 定理(REACT) [OP 01] ハッシュ関数GおよびHに対するランダムオラクルモデルにおいて、 (Gen,Enc,Dec)が平文検査攻撃に対し一方向ならば、 構成(REACT)は適応的選択暗号文攻撃に対し識別不可能である。 証明 双子エルガマル暗号 G= g について、 DHタプル： (g, gx, gy, gxy) 双子DHタプル： (g, gx1, gx2, gy, gx1y, gx2y). 仮定(双子計算DH仮定) 双子DHタプルを判定してくれるオラクルが与えられても、 双子DHタプルの計算は困難であるという仮定を双子計算仮定という。 より正確には、 群生成アルゴリズムGenGに対して双子計算DH仮定が成り立つとは、 任意の効率的なアルゴリズムAについて、その成功確率 Pr[s=(q,g) ← GenG(1n), X1,X2,Y ← g ： A2dhpg(X1,X2,・,・,・)(X1,X2,Y) = 2dhg(X1, X2, Y)] がネグリジブルであることをいう。ここで、 2dhg(X1, X2, Y) =def (gx1 y, gx2 y), 2dhpg(X1, X2, Y, Z1, Z2) =def 『 2dhg(X1, X2, Y) =? (Z1, Z2) 』. 命題(双子計算DH仮定) 計算DH仮定のもとで、双子計算DH仮定は真である。 証明 構成(双子エルガマル暗号) (E, D) 鍵空間Kをもつ共通鍵暗号 H {0,1}* → K ハッシュ関数 Gen(1n) (q, g) ← GenG(1n) x1, x2 ← Zq, X1 = gx1, X2 = gx2 pk=(q,g,X1,X2), sk = (q,g,x1,x2). Enc(pk, m) y ← Zq Y = gy, Z1 = X1y, Z2 = X2y, k = H(Y,Z1,Z2) return (Y, c = E(k, m)). Enc(sk, (Y,c)) Z1 = Yx1, Z2 = Yx2, k = H(Y,Z1,Z2) return m = D(k, c). 定理(双子エルガマル暗号) ハッシュ関数Hに対するランダムオラクルモデルにおいて、 GenGが計算DH仮定を満たし、共通鍵暗号(E,D)が適応的選択暗号文攻撃に対し識別不可能であるならば、 双子エルガマル暗号は適応的選択暗号文攻撃に対し識別不可能である。 ランダムオラクルモデルを必要としない構成 Cramer-Shoup暗号 構成(CS暗号) Gen(1n) ハッシュ関数 H {0,1}* → Zq を選択。 (q, g1, g2) ← GenG(1n) x, y, a, b, a , b ← Zq h = g1x g2y, c = g1a g2b, d = g1a g2b pk = (g1,g2,h,c,d,H), sk = (x,y,a,b,a ,b ). Enc(pk, m) // m ∈ g1 r ← Zq, α = H(g1r, g2r, hrm) return C = (g1r, g2r, hrm, (cdα)r). Dec(sk, C=(u,v,w,e)) α = H(u, v, w) ua+αa vb+αb ≠ e return ⊥ else return w / (uxvy). 定理(CS暗号) ハッシュ関数Hが衝突困難で、GenGが決定DH仮定を満たすならば、 CS暗号は適応的選択暗号文攻撃に対し識別不可能である。 証明 Camenish-Shoup暗号 仮定(DCR仮定) 整数 n (=pq) を与えられて、 Zn2* のランダム要素と(Zn2*)nのランダム要素を識別できない とき、 Decision Composite Residuosity (DCR) 仮定が成り立つという。 abs Zn2* → Zn2* abs(a) = (n2 - a) mod n2 ( if a n2 / 2 ) abs(a) = a mod n2 otherwise 構成(Camenish-Shoup暗号) Gen(1l) ハッシュ関数 H {0,1}* → [2l] p , q lビットの異なる Sophie-Germain 素数 p = 2p + 1, q = 2q + 1, n = pq, n = p q x1, x2, x3 ← [n2/4], g ← Zn2* g = (g )2n, y1 = gx1, y2 = gx2, y3 = gx3 pk = (H, n, g, y1, y2, y3), sk = (H, n, x1, x2, x3). Enc(pk, m, L) // m ∈ [n], Lはラベル r ← [n/4] u = gr, e = y1r hm, v = abs( (y2y3H(u,e,L))r ) return (u, e, v). Dec(sk, (u,e,v), L) abs(v) =? v u2(x2 + H(u,e,L)x3) =? v2 t = 2-1 mod n m = (e / ux1)2t m が hm (∃m ∈ [n]) の形ならば、m を出力。 そうでないならば、reject. 定理(Camenish-Shoup暗号) ハッシュ関数Hが衝突困難で、DCR仮定が成り立つならば、 Camenish-Shoup暗号は適応的選択暗号文攻撃に対し識別不可能である。 タグベース暗号 タグベース暗号とは、 効率的な確率的アルゴリズムの3つ組(Gentbe, Enctbe, Dectbe)である： (pk, sk) ← Gentbe(1n) c ← Enctbe(pk, t, m) m ← Dectbe(sk, t, c). 完全性(completeness)条件として、 全てのメッセージm(∈M)とすべてのタグt(∈T)について Pr[ (pk, sk) ← Gentbe(1n), c ← Enctbe(pk, t, m), m ← Dectbe(sk, t, c) m = m ] = 1 を要求する。 タグ選択暗号文攻撃に対する識別不可能性 タグベース暗号TBE=(Gentbe,Enctbe,Dectbe)とそれに対する攻撃者Aについて： 試行 StagCCATBE,A(n) (t*, st0) ← A(1n) (pk, sk) ← Gentbe(1n) (M0, M1, st) ← ADectbe(・,・)(pk, st0) b ← {0,1}, c* ← Enctbe(pk, t*, Mb) b ← ADectbe(・,・)(c*, st) return b =? b . ただし、Aは復号オラクルDectbe(・,・)にタグt*について問い合わせることは許されない。 定義(IND-STAG-CCA) タグベース暗号TBEがタグ選択暗号文攻撃に対し識別不可能(IND-STAG-CCA)であるとは、 任意の効率的な攻撃者Aについて、その識別利得 ｜ Pr[ StagCCATBE,A(n) = 1 ] - 1/2 ｜ がネグリジブルであることをいう。 タグベース暗号から公開鍵暗号への変換 構成(TBE2PKE) TBE = (Gentbe, Enctbe, Dectbe) タグ空間Tのタグベース暗号 OTS = (SKG, SIGN, VFY) ワンタイム署名 (s.t. vk ∈ T) PKE = (Genpke, Encpke, Decpke) 公開鍵暗号 Genpke = Gentbe. Encpke(pk, m) (vk, sigk) ← SKG(1n) ctbe ← Enctbe(pk, vk, m) σ ← SIGN(sigk, ctbe) return c = (ctbe, vk, σ). Decpke(sk, c) (ctbe, vk, σ) = c VFY(vk, ctbe, σ) =? reject return ⊥ else return m = Dectbe(sk, vk, ctbe). 定理(TBE2PKE) [Kiltz 06] TBEがタグ選択暗号文攻撃に対し識別不可能なタグベース暗号で、 OTSがストロングワンタイム署名ならば、 PKE = TBE2PKE(TBE, OTS) は適応的選択暗号文攻撃に対し識別不可能である。 証明 タグ選択暗号文攻撃に対し識別不可能なタグベース暗号の構成 判定線形仮定 群G= g について、 線形タプル (g1, g2, z, g1r1, g2r2, zr1+r2). 定義(判定線形仮定) 群Gについて、与えられた6要素からなるタプル (g1, g2, z, g1r1, g2r2, w) が線形タプルかランダムタプルかを判定する問題を判定線形問題という： w =? zr1+r2. 判定線形問題が困難であるとの仮定を判定線形仮定という。 命題(DLinear) 判定線形仮定は判定DH仮定よりも弱い仮定である（より妥当な仮定である）。 すなわち、判定線形問題が解けるときは判定DH問題も解ける。 証明 命題(DLinear)は、判定DH問題が解けても判定線形問題は解けない、という可能性は除外しない。 実際、双線形群にはそのような可能性を期待できる。 ある群Gについて、判定DH問題は易しいのに判定線形問題はむずかしいとき、 群Gは判定線形ギャップ仮定をみたすという。 注意 (g, gx1, gx2, gy, gx1y, gx2y)：双子DHタプル ⇒ (gy-1, gy-1, g, gx1, gx2, gx1y+x2y) 線形タプル 判定線形仮定にもとづくタグ選択暗号文攻撃に対し識別不可能なタグベース暗号 構成(LinearTBE) [Kiltz 06] Gentbe(1n) G 位数q の群 g1 ← G, (x1,x2,y1,y2) ← Zq g2, z を g1x1 = g2x2 = z となるようにとる。 u1 = g1y1, u2 = g2y2 pk = (q, g1, g2, z, u1, u2), sk = (x1, x2, y1, y2). ※ (g1, g2, z, -, -, -)は判定線形問題の問題文の一部。 ※ 秘密鍵skを知っていれば、この問題文（の一部）に関する判定線形問題は容易： ※ (g1, g2, z, c1, c2, w)は線形タプル ⇔ c1x1 c2x2 = w. Enctbe(pk, t, m) r1,r2 ← Zq*, c1 = g1r1, c2 = g2r2 d1 = ztr1 u1r1, d2 = ztr2 u2r2, e = m zr1+r2 return ctbe = (c1, c2, d1, d2, e). ※ (g1, g2, z, c1, c2, zr1+r2)は線形タプル。 ※ 実際、c1x1 c2x2 = zr1+r2. ※ d1, d2はc1, c2の正当性を示す： ※ c1tx1+y1 = d1, c2tx2+y2 = d2. Dectbe(pk, t, ctbe) s1,s2 ← Zq* k = (c1x1+s1(tx1+y1) c2x2+s2(tx2+y2)) / (d1s1d2s2) ※ 正当な暗号文、すなわち citxi+yi = di (i=1,2) のときだけ、まともに復号される。 ※ k = c1x1 c2x2 = zr1+r2. return m = e / k. (パブリック検証) Pvtbe(pk, t, ctbe) 暗号文の正当性は公開情報だけで確認できる return DH(g1, zt u1, c1, d1) ∧ DH(g2, zt u2, c2, d2). ※ ⇔ di = citxi+yi (for i=1,2). 定理(LinearTBE) [Kiltz 06] 群Gに対する判定線形ギャップ仮定のもとで、 構成(LinearTBE)はタグ選択暗号文攻撃に対し識別不可能なタグベース暗号である。 証明 上へ